/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    void InOrder(Node* root)
    {
        if(root==nullptr)return;
        InOrder(root->left);
        //尾插
        if(_head==nullptr)
        {
            _head=_pre=root;
        }
        else
        {
            _pre->right=root;
            root->left=_pre;
            //更新pre
            _pre=root;
        }
        InOrder(root->right);
    }  

    Node* treeToDoublyList(Node* root) {
        if(root==nullptr)return nullptr;

        InOrder(root);//中序遍历进行尾插
        //构建循环
        _head->left=_pre;
        _pre->right=_head;

        return _head;
    }
private:
    Node* _head=nullptr;
    Node* _pre=nullptr;

};